Crveno-Crni stebla (makedonski)
Vrsta: Seminarski | Broj strana: 9 | Nivo: Fakultet za elektrotehnika i informaticka tehnologioja

Вовед
Повеќето операции на бинарните пребарувачки стебла (дрва) имаат време кое е пропорционално со висината на стеблото, па затоа е пожелно нивната висина да биде што помала. Обичните бинарни пребарувачки стебла имаат недостаток што тие може да имаат многу големи разлики во висините на подстеблата, а најчесто ова се случува поради редоследот на внесувањето на клучевите. Резултатот во ваквите случаи може да биде податочна структура слична на поврзана листа, при што сите операции во стеблото стануваат скапи. Доколку податоците се знаат пред внесувањето, може да се „држи“ висината мала со начинот на кој тие ќе се додаваат, меѓутоа ова секогаш не е случај.
Балансирани бинарни стебла
Само-балансираните бинарни стебла го решаваат овој проблем со изведба на трансформации во стеблото (како што е ротација на стеблото) за време на додавањето на клучот, со цел да се намали висината. Иако за ова е потребно време, операциите кои ќе се извршуваат подоцна ќе бидат далеку побрзи за разлика од не балансирано стебло.
Висината може да биде најмногу log2n, а постојат најмногу 2k јазли на k-тото ниво – комплетно или полно бинарно стебло може да има токму волку нивоа. Балансираните пребарувачки стебла секогаш не се прецизно балансирани, бидејќи понекогаш може да биде скапо да се чува стеблото балансирано постојано, па затоа голем број на алгоритми ја чуваат висината со константен фактор од можната граница.
Во табела 1 се дадени времињата на најчестите операции во зависност од јазлите во стеблото.
Табела 1: Времиња на операции во зависност од јазлите во стеблото (n).
Операција Време Пребарување O(log n) Вметнување O(log n) Отстранување O(log n)
За некои имплементации ова се најлошите времиња, додека други имплементации се извршуваат подобро од ова.
Постојат повеќе податочни структури кои ги имплементираат овие стебла, меѓу нив позначајни се:
Црвено-црно стебло (анг. Red black tree),
AA стебло,
AVL стебло,
Жртвен јарец стебло (анг. Scapegoat tree),
Проширено стебло (анг. Splay tree) и др.
Балансираните бинарни пребарувачки стебла можат да се користат за конструирање и одржување на подредени листи, како редовите на приоритет.
Тие може да се користат за асоцијативни низи. Паровите клуч-вредност едноставно се внесуваат врз база на клучот. Во овој случај, овие стебла имаат голем број на предности (но и недостатоци) врз главниот конкурент – хаш табелите (анг. hash tables).
Многу алгоритми може да ги користат балансираните стебла за да постигнат најдобри лоши граници со малку напор. На пример, ако бинарно сортирачко стебло е направено со балансирано стебло, има многу едноставен асимптотски оптимален O(n log n) сортирачки алгоритам. Слично, други алгоритми во геометријата користат варијации на балансирани стебла за да разрешат проблеми како проблемот на вметнување на линиски сегмент.

---------- CEO RAD MOŽETE PREUZETI NA SAJTU. ---------- 

www.maturski.org 

 

MOŽETE NAS KONTAKTIRATI NA E-MAIL: [email protected]